public class Sort2 {
    // 归并排序---递归
 public static void mergeSort(int[] array){
     mergeChild(array,0, array.length-1);

    }

    private static void mergeChild(int[] array, int left, int right) {
     //递归结束的条件
        if (left>=right){
            return;
        }
     //先分，递归将数据分成左右两份
        int mid=(left+right)/2;
        //递归mid下标的左边
        mergeChild(array,left,mid);
        //递归mid下标的右边
        mergeChild(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
     int[] tmp=new int[right-left+1];
     int k=0;
     int s1=left;
     int e1=mid;
     int s2=mid+1;
     int e2=right;
     while (s1<=e1&&s2<=e2){
         if (array[s1]<array[s2]){
             tmp[k++]=array[s1++];
         }else {
             tmp[k++]=array[s2++];
         }
     }
     if(s1<=e1){
         tmp[k++]=array[s1++];
     }
     if (s2<=e2){
         tmp[k++]=array[s2++];
     }
     //将tmp里面的数据拷贝回array数组里面去
        for (int i = 0; i < tmp.length; i++) {
            array[i+left]=tmp[i];
        }
    }

    // 归并排序---非递归
public static void mergeSort2(int[] array){
       //定义一个gap=1
    int gap=1;
    while (gap<array.length){
        for (int i = 0; i < array.length; i=i+2*gap) {
            int left=i;
            int mid=left+gap-1;
            if (mid>=array.length){
                mid=array.length-1;
            }
            int right=mid+gap;
            if (right>=array.length){
                right=array.length-1;
            }
            merge(array,left,mid,right);
        }
        gap*=2;
    }
    }
}
